/*
 * @Author: 缄默
 * @Date: 2021-12-09 20:53:18
 * @LastEditors: 缄默
 * @LastEditTime: 2021-12-09 22:24:47
 */

//最长公共子序列

#include <iostream>
#include <vector>
#include <string>
#include <math.h>

using namespace std;

string lcse(string s1, string s2);
vector<vector<int>> getdp(string s1, string s2);

int main() {

    string s1 = "1a2c3d4b56";
    string s2 = "b1d23ca45b6a";
    cout << lcse(s1, s2) << endl;
    return 0;
}

//找到最长公共子序列的dp数组
vector<vector<int>> getdp(string s1, string s2) {
    vector<vector<int>> res(s1.size(), vector<int>(s2.size()));
    //初始化dp数组第一行和第一列
    res[0][0] = s1[1] == s2[2] ? 1 : 0;
    for (int i = 1; i < s1.size(); i++) {
        res[i][0] = max(res[i - 1][0], s1[i] == s2[0] ? 1 : 0);
    }
    for (int i = 1; i < s2.size(); i++) {
        res[0][i] = max(res[0][i - 1], s2[i] == s1[0] ? 1 : 0);
    }
    //根据第一行和第一列
    for (int i = 1; i < s1.size(); i++) {
        for (int j = 1; j < s2.size(); j++) {
            //res[i][j]不增
            res[i][j] = max(res[i - 1][j], res[i][j - 1]);
            //如果相等res[i][j]加一
            if (s1[i] == s2[j]) {
                res[i][j] = max(res[i][j], res[i - 1][j - 1] + 1);
            }
        }
    }
    return res;
}

string lcse(string s1, string s2) {
    if (s1.size() == 0 || s2.size() == 0) return "";
    vector<vector<int>> dp = getdp(s1, s2);
    int m = s1.size() - 1;
    int n = s2.size() - 1;
    string res(dp[m][n], '0');
    int index = dp[m][n] - 1;
    while (index >= 0) {
        if (n > 0 && dp[m][n] == dp[m][n - 1]) {
            n--;
        }
        else if (m > 0 && dp[m][n] == dp[m - 1][n]) {
            m--;
        }
        else {
            res[index--] = s1[m];
            m--;
            n--;
        }
    }
    return res;
}
